1) On considère p objets numérotés de 1 à p et n boîtes numérotées de 1 à n. On suppose p = n = 4.
Il y a 4 façons de ranger le premier, puis, pour chacune de ces façons, 3 de ranger le deuxième etc. Il y a donc en tout 4 x 3 x 2 x 1 = 4! façons de ranger les objets.
|
p = 4 |
p! = 1 x 2 x 3 x 4 = 24 |
|
p = 5 |
p! = 1 x 2 x 3 x 4 x 5 = 5 x 4! = 120 |
|
p = 10 |
p! = 3 628 800 |
|
p = 20 |
p! = 2 432 902 008 176 640 000 |
|
p = 100 |
p! incalculable. |
2) On suppose maintenant que le nombre de boîtes est différent du nombre d’objets. Pour p = 3 et n = 5, il y a 5 façons de ranger le premier, puis, pour chacune de ces façons, 4 de ranger le deuxième et 3 de ranger le troisième. Il y a donc en tout 5 x 4 x 3 = 60 façons de ranger les objets.
La formule générale, pour n boîtes et p objets, est :
n x (n – 1) x (n – 2) x … x (n – p + 1) = n! / (n – p)!
|
p = 4, n = 6 |
6! / 2! = 30 |
|
p = 4, n = 7 |
7! / 3! = 820 |
|
p = 5, n = 8 |
8! / 5! = 336 |
3) On choisit trois boîtes parmi les 5 dans lesquelles on place 3 objets. D’après la première question, il y a 3! = 6 façons de ranger les 3 objets.
Si l’on choisit trois autres boîtes, il y a encore 3! façons de ranger les 3 objets.
Soit C53 le nombre de façons de choisir trois boîtes parmi les 5. On a, d’après la question précédente :
3! x C53 = 5 x 4 x 3
D’où :
C53 = 5 x 4 x 3 /3! = 10
Dans le cas général de n boîtes et de p objets, on sait que le nombre total de ranger les p objets dans les n boîtes est égal à n! / (n – p)! . On sait qu’il y a p! façons de ranger les p objets dans p boîtes choisies.
Soit Cnp le nombre de façons de choisir p boîtes parmi les n. On a, d’après la question précédente :
Cnp
= (n – p + 1)! /p!
On obtient la formule générale du nombre de façons de choisir trois boîtes parmi n :
|
Cnp
= n! / [p! x (n – p)!] |
4) La formule ci-dessous est évidente : choisir p boîtes parmi n revient à choisir les n – p autres :
Cnp = Cnn – p
On a donc :
|
Cnp |
= |
n! / [p! x (n – p)!] |
|
Cnp + 1 |
= |
n! / [(p + 1)! x (n – p – 1)!] |
Le dénominateur commun est (p + 1)! (n – p)!. On réduit au dénominateur commun en multipliant le numérateur et le dénominateur de Cnp par (p + 1). et le numérateur et le dénominateur de Cnp + 1 par (n – p). La somme est alors égale à :
|
n! (p + 1) + n!(n – p) |
|
n! (p + 1 + n – p) |
n! (n + 1) |
|
_________________________ |
= |
_________________________ |
_________________________ |
|
[(p + 1) x (n – p)!] |
|
[(p + 1) x (n – p)!] |
[(p + 1) x (n – p)!] |
On reconnaît dans le second membre Cn + 1p + 1 et on a donc :
|
Cnp
+ Cnp + 1 |
= |
Cn
+ 1p + 1 |
5) On considère un ensemble E comportant n éléments. La construction d’un sous-ensemble repose sur le choix de ses éléments. On suppose que les éléments sont numérotés de 1 à n.
On considère le premier élément. Il y a deux choix possibles : soit il appartient à l’ensemble, soit il ne lui appartient pas. Une fois ce choix effectué, il y a encore deux choix possibles pour l’élément suivant, … Il y a donc en tout 2 x 2 x 2 …x 2 = 2n choix possibles pour construire un sous ensemble de E. Le nombre de sous-ensembles est donc égal à 2n. on peut éventuellement le démintrer par récurrence.
Par ailleurs, il y a Cnp façons de choisir p éléments parmi n et donc Cnp sous-ensembles comportant p éléments. La somme des nombres d’ensembles comportant 0 éléments (l’ensemble vide), 1 (Cn1) , 2 ( Cn2) …, est égale au nombre total d’ensemble que l’on peut construire. On a donc :
|
n |
|
|
S |
Cnk = 2n |
|
k = 0 |
|
Une autre façon de montrer cette égalité consiste à développer la puissance (1 + 1)n suivant la formule du binôme.